package priorityqueue

import (
	"gostl/stl/vector"
)

// 这是一个类似于C++STL库的优先级队列实现

type priority_queue[T any] struct {
	data *vector.Vector[T]
	cmp  Comparator[T] //建立大堆还是小堆
}

func New[T any](opt Comparator[T]) *priority_queue[T] {
	queue := &priority_queue[T]{
		data: vector.New[T](),
		cmp:  opt,
	}
	return queue
}

// 向上调整s
func (q *priority_queue[T]) adjust_up() {
	child := q.data.Size() - 1
	parent_pos := ((child - 1) / 2)
	//调整堆结构
	for child > 0 {
		//先找到插入位置元素的父节点
		child_val, _ := q.data.At(child)
		parent_val, _ := q.data.At(parent_pos)
		if q.cmp.compare(child_val, parent_val) {
			Swap(q.data.GetAtPtr(parent_pos), q.data.GetAtPtr(child))
			//继续沿着父节点向上更新
			child = parent_pos
			parent_pos = (child - 1) / 2
		} else {
			break
		}
	}
}

// 向下调整
func (q *priority_queue[T]) adjust_down() {
	parent := 0
	child := (parent*2 + 1)
	for child < q.data.Size() {
		if child+1 < q.data.Size() && q.cmp.compare(q.at(child+1), q.at(child)) {
			child++
		}
		//开始向下调整
		if q.cmp.compare(q.at(child), q.at(parent)) {
			Swap(q.data.GetAtPtr(child), q.data.GetAtPtr(parent))
			parent = child
			child = (parent*2 + 1)
		} else {
			//注意break
			break
		}
	}
}

// 实现一个堆
func (q *priority_queue[T]) Push(val T) {
	q.data.PushBack(val)
	//向上调整
	q.adjust_up()
}

func (q *priority_queue[T]) Pop() {
	Swap(q.data.FirstPtr(), q.data.BackPtr())
	q.data.PopBack()
	//向下调整
	q.adjust_down()
}
func (q *priority_queue[T]) Top() (T, error) {
	res, err := q.data.Front()
	if err == nil {
		return res, nil
	}
	return res, err
}
func (q *priority_queue[T]) Size() int {
	return q.data.Size()
}
func (q *priority_queue[T]) Empty() bool {
	return q.data.Empty()
}

// 只能内部使用,一定成功，不会返回不合法的数据
func (q *priority_queue[T]) at(index int) T {
	res, _ := q.data.At(index)
	return res
}
